#leetcode题目139：单次拆分
#难度：中等

#方法：动态规划


#问题拆解：
#1.单词组合能否拼接成字符串
#2.字符串中的片段能否与单词匹配

#转换成树的方式，可以加速整个搜索过程，也就是字典树
#字典树的特点是

from typing import List

class TreeNode:
    """字典树节点"""
    def __init__(self):
        self.children = [None] * 26  # 26个小写字母
        self.is_end_of_word = False  # 标记是否是单词结尾

class Tree:
    """字典树"""
    def __init__(self):
        self.root = TreeNode()
    
    def add(self, word: str) -> None:
        """添加单词到字典树"""
        curr = self.root
        for char in word:
            idx = ord(char) - ord('a')
            if curr.children[idx] is None:
                curr.children[idx] = TreeNode()
            curr = curr.children[idx]
        curr.is_end_of_word = True

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        """
        单词拆分
        给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，
        判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
        """
        # 构建字典树
        tree = Tree()
        for word in wordDict:
            tree.add(word)
        
        n = len(s)
        # dp数组用于记忆化：
        # 0: 未计算
        # 1: 可以拆分 (True)
        # -1: 不能拆分 (False)
        dp = [0] * n

        def process(index: int) -> bool:
            """
            递归处理函数
            :param index: 当前处理的起始位置
            :return: 从index开始是否可以拆分
            """
            # 基础情况：如果已经到达字符串末尾，说明可以拆分
            if index == n:
                return True
            
            # 记忆化检查：如果已经计算过，直接返回结果
            if dp[index] != 0:
                return dp[index] == 1
            
            res = False
            curr_node = tree.root
            
            # 从当前位置开始尝试形成单词
            for i in range(index, n):
                char_idx = ord(s[i]) - ord('a')
                
                # 移动到字典树的下一个节点
                if curr_node.children[char_idx] is None:
                    # 当前前缀不在字典中，无法继续
                    break
                curr_node = curr_node.children[char_idx]
                
                # 如果当前节点标记为单词结尾
                if curr_node.is_end_of_word:
                    # 递归检查剩余部分是否可以拆分
                    if process(i + 1):
                        res = True
                        break  # 优化：找到一个可行解就停止
            
            # 将结果存储到dp数组中
            dp[index] = 1 if res else -1
            return res
        
        return process(0)


#测试数据
s = "leetcode"
wordDict = ["leet", "code"]
#预期输出：True
solution = Solution()
print(solution.wordBreak(s, wordDict))


s = "applepenapple"
wordDict = ["apple", "pen"]
#预期输出：True
solution = Solution()
print(solution.wordBreak(s, wordDict))


s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
#预期输出：False
solution = Solution()
print(solution.wordBreak(s, wordDict))


